Random number generation is used in widely differing fields, ranging from simulations, e.g., Monte Carlo methods, telecommunication systems, e.g., for selecting spread spectrum frequencies to gambling, etc. Although, the quality of the random numbers used is important for all of these fields, it takes on particular importance in the field of cryptography.
In cryptography, random numbers are used for many purposes and often the security of a cryptographic system hinges on the quality of the random numbers. For example, key generation frequently employs a source of random numbers. Other applications of random numbers in cryptography include the generation of a nonce, generation of a challenge for use in a challenge-response protocol, as initialization vector, for example as the initialization vector for a block cipher running in CBC mode.
Other security applications may also employ random numbers, for example, countermeasures against side channel analysis may employ blinding of secret information with a random blinding number.
In these applications, if the random numbers are not sufficiently random, they compromise the security of the cryptographic application in which they are used.
A sequence of random number is preferably unpredictable. Thus an attacker cannot predict a sequence before it has been produced better than chance. Similarly, the sequence cannot be reliably reproduced. After a sequence has been produced it is not feasible to produce it again.
For unpredictable sequence it is infeasible given the security demands of the application to predict what the next random bit will be, even if one has complete knowledge of the algorithm, of the hardware generating the sequence, and all of the previously generated bits.
A true random number sequence has all of these properties, but they may also be obtained from a deterministic random number sequence if it has a suitably random seed.
The objects that a random number generator produces may be interpreted in various ways, as numbers, typically from some pre-determined range, as characters, or as bits, etc. A sequence of bits may be mapped to a sequence of numbers and vice versa. The term random bit generator is also used, and may be regarded as a random number generator which generates random integral numbers between 0 and 1. What applies to a random bit generator applies also mutatis mutandis to a random number generator and vice versa.
Random bit generators (RBGs) may be divided into two classes. The random number generators in one class produce bits non-deterministically, where every bit of output is based on a physical process that is unpredictable; these random bit generators are commonly known as non-deterministic random bit generators (NRBGs). The random number generators in the other class compute bits deterministically using an algorithm; this class of RBGs is known as Deterministic Random Bit Generators (DRBGs). An NRBGs is also referred to as a true random number generator. A DRBG is also referred to as a pseudo random number generator.
A Deterministic Random Bit Generator is typically initiated with a seed. A seed is a limited sequence of numbers, e.g. a string of bits used as input to a deterministic random number generator. The seed will determine all or a portion of an internal state of the generator. The entropy of the seed must be sufficient to support the security requirements of the DRBG. The seed may be obtained from a true random number generator.
Deterministic Random Bit Generators are further described in NIST Special Publication 800-90, Recommendation for Random Number Generation Using Deterministic Random Bit Generators, March 2007. We will refer to this publication as the NIST standard.
Most true random number generators use thermal noise as the random process. For example, thermal noise in integrated circuits describes small voltage fluctuations that exist on conductors in equilibrium. Other sources of randomness include decay of radioactive material, quantum mechanics processes, frequency instability of free-running oscillators, etc.
An additional source of true random numbers is described in: D. Holcomb, W. Burleson, K. Fu, Power-up SRAM State as an Identifying Fingerprint and Source of True Random Numbers, IEEE Transactions on Computers, 2009. In the paper it is described that an SRAM may be used as a true random number generator, since the memory content of an SRAM is partially random after the SRAM has been powered-up.